\documentclass{ctexart}
\bibliographystyle{IEEEtran}
\usepackage{booktabs}
\usepackage{url}
\usepackage{algorithm,algorithmic}
\usepackage{listings}
\usepackage{xcolor}
\usepackage{tikz}
\pagestyle{plain}
\title{BinarySearchTree的建立}
\author{张祺\\信息与计算科学 2101  3210104145}
\date{2022年10月19日}
\begin{document}
\maketitle
\section{设计思路}
在main函数中，我设计了两个函数：BSTSorting、Test。BSTSorting用来将输入的特定vector构建成二叉树的形式，Test用来自动生成制定范围的vector，并且对将这些vector排序成二叉树的过程计时输出。
\subsection{void BSTSorting( const std::vector<Comparable> \& \_{}arr, int \_{}mode = 0 )}
\verb|_arr|为待排序的输入vector，\verb|_mode|为vector是否需事先乱序的判断标准。
在函数内部我定义了一个二叉树类实例rng，用以对\verb|_arr|内部数据进行排序，当\verb|_mode = 0|时，无需对\verb|_arr|内部数据做任何修改，直接通过for，以及BinarySearchTree的公共函数insert构建出一株二叉树;当\verb|_mode = 1|时，先通过\verb|random_shuffle|对\verb|_arr|内部数据乱序后，再重复前述操作构建二叉树。
\subsection{void Test( const int \& length, int times )}
length为自动生成测试样例vector的长度，times为重复实验的次数。
首先利用while循环生成一个顺序的vector，然后通过ctime头文件引入\verb|clock_t、CLOCKS_PER_SEC|用以计算排序算法的效率，并且直接输出duration。
\subsection{int main()}
包含九个测试样例，并且通过while使得可以通过键盘输入来自行测试。
\section{测试说明}
\subsection{样例说明}
共有九个测试样例，前五个为数组长度十倍增长，重复实验次数为十;后四个为数组长度保持为1000不变，重复实验次数由100十倍增长至100000.
\subsection{结果分析}
\subsubsection{}
由下表中数据我们可以看出，在实验重复次数不变时，随着数组长度的增长，完成二叉树排序的时间呈现出更快的倍数增长，并且对乱序后的数组进行排序都能在一定程度上减少所需的时间，而数组长度越长，这种差异也越明显。\par
对于这种差异的产生我认为和二叉树排序算法的构建有着密切的关系，在搭建一棵二叉树时，我们总要找到树的叶子去插入新的数据，而在经乱序前的数组中，我们可以发现树是不均衡的，极端情况下是一条向右倾斜的直线，这就意味着我们在插入新的叶子时需要重新遍历之前的所有数据，这会使得我们的效率大大下降;而在我们将数组乱序后，我们所构建的二叉树更有可能是一棵满树，这就意味着我们可以通过更少的步数就插入新的数据，这会大大地加快我们的效率。
\begin{center}
\begin{tabular}{|c|c|c|c|c|c|} \hline
  (length, times) & (10, 10) & (100, 10) & (1000, 10) & (10000, 10) & (100000, 10) \\ \hline
  mode = 0 & 2e-06 & 2.7e-05 & 0.002205 & 0.265961 & 44.0138 \\ \hline
  mode = 1 & 1.9e-06 & 7.6e-06 & 0.0001191 & 0.0021344 & 0.0342525 \\ \hline
\end{tabular}
\end{center}
\subsubsection{}
由下表中数据我们可以看出，在数组长度固定时，随着实验重复次数的增加，完成二叉树排序的时间在一固定值区间内摇摆，而且实验重复次数的增加并无法明显的看出收敛于某特定值(可能是电脑的物理电子元件的性状导致）。
\begin{center}
\begin{tabular}{|c|c|c|c|c|c|} \hline
  (length, times) & (1000, 100) & (1000, 1000) & (1000, 10000) & (1000, 100000) \\ \hline
  mode = 0 & 0.002075 & 0.002203 & 0.002098 & 0.002132 \\ \hline
  mode = 1 & 0.00010827 & 0.000108818 & 0.000103478 & 0.000105519 \\ \hline
\end{tabular}
\end{center}
\subsection{结论}
当数组内的数据结构较为混乱时，使用二叉树排序算法将其排序所需要的时间，远小于排序数据较为整齐的数组。
\end{document}
